package com.javaDemo.ti;

/**
 * @ClassName: Dancisousu
 * @Auther: csy https://leetcode-cn.com/problems/word-search/
 * @Date: 2021/3/12 09:34
 * @Description: 回溯法
 */
public class Dancisousu {
    private static final int dir[][]={{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
    static boolean[][] flag;
    static boolean hasfind=false;
    static char board[][]={{'A','B','C','E'}, {'S','F','C','S'}, {'A','D','E','E'}};
    static int col=board[0].length;
    static int row=board.length;

    public static void main(String[] args) {
        String word="ABC";
        Boolean result=search(board,word);
        System.out.println(result);
    }

    private static Boolean search(char[][] board, String word) {
        flag = new boolean[row][col];
        char[] chars=word.toCharArray();
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                backTrack(board,chars,1,i,j);
                if(hasfind){
                    return true;
                }
            }
        }
        return false;
    }

    private static void backTrack(char[][] board, char[] chars, int current, int x, int y) {
        if(hasfind){
            return;
        }
        if(current==chars.length){
            hasfind=true;
            return;
        }
        flag[x][y] = true;
        for(int[] dire : dir){
            int newX = x + dire[0], newY = y + dire[1];
            if(isIn(newX, newY) && !flag[newX][newY] && board[newX][newY] == chars[current]) {
                backTrack(board, chars, current + 1, newX, newY);
            }
        }
        flag[x][y] = false;

    }
    private static boolean isIn(int x, int y){
        return x >= 0 && x < row && y >= 0 && y < col;
    }

}
